public class Test1 {
    //leetcode 累加数
    //https://leetcode.cn/problems/additive-number/description/?envType=problem-list-v2&envId=backtracking

    /**
     * 题目关键是确定最开始的两个数
     * @param num
     * @return
     */
    public boolean isAdditiveNumber(String num) {
        int n = num.length();
        // 遍历第一个数的结束位置 i
        for (int i = 1; i <= n / 2; i++) {
            // 第一个数不能有前导零，除非它本身是 "0"
            if (num.charAt(0) == '0' && i > 1) {
                break;
            }
            long num1 = Long.parseLong(num.substring(0, i));

            // 遍历第二个数的结束位置 j
            for (int j = i + 1; Math.max(i, j - i) <= n - j; j++) {
                // 第二个数不能有前导零，除非它本身是 "0"
                if (num.charAt(i) == '0' && j - i > 1) {
                    break;
                }
                long num2 = Long.parseLong(num.substring(i, j));

                // 检查剩下的部分是否符合条件
                if (isValid(num, j, num1, num2)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean isValid(String num, int start, long num1, long num2) {
        while (start < num.length()) {
            num2 += num1;
            num1 = num2 - num1; // 更新 num1
            String sum = String.valueOf(num2);

            // 检查 num 从 start 开始是否以 sum 开头
            if (!num.startsWith(sum, start)) {
                return false;
            }
            start += sum.length(); // 更新起始位置
        }
        return true;
    }
}
